package 简单.链表;

import util.ListNode;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 * <p>
 * 题目数据 保证 整个链式结构中不存在环。
 * <p>
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
 */
public class 相交链表_160 {

    public static void main(String[] args) {

    }

    /**
     * 双指针
     * 因为两链表到达相同节点的距离不一样
     * 当两条链表长度不一样时，其实长链表多余的部分是不可能相交的，是多余的
     * A 7  B 5
     * 如何让链表长度一样？
     * 1，
     * 在A的链表前面加上B链表
     * 在B的链表前面加上A链表
     * -->
     * 5+7 -->7前面2位变成无用的了
     * 7+5
     * 2，
     * 先让A走两步，然后一起走
     * <p>
     * 4567123
     * 23123
     * -->listA+listB,listB+listA
     * 456712323 123
     * 231234567 123
     * -------
     * 4567123
     * 231131
     * -->
     * 4567123231131
     * 2311314567123
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        //不能改变原链表
        ListNode A = headA;
        ListNode B = headB;
        //都为null或者相等
        while (A != B) {
            if (A != null) {
                A = A.next;
            } else {
                A = headB;
            }
            if (B != null) {
                B = B.next;
            } else {
                B = headA;
            }
        }
        return B;
    }


}
